package business.histocloud.algorithm.delaunay;

import java.util.ArrayList;
import java.util.List;
import business.histocloud.component.DrawBox;

/**
 * Incremental Delaunay Triangulation
 *
 * @author Java-code by X.Philippeau - Pseudo-code by Guibas and Stolfi
 *
 * @see Primitives for the Manipulation of General Subdivisions and the
 * Computation of Voronoi Diagrams (Leonidas Guibas,Jorge Stolfi)
 */
public class Delaunay {

    // starting edge for walk (see locate() method)
    private QuadEdge startingEdge = null;

    // list of quadEdge belonging to Delaunay triangulation
    private final List<QuadEdge> quadEdge = new ArrayList<>();

    // Bounding box of the triangulation
    class BoundingBox {

        int minx, miny, maxx, maxy;
        DrawBox a = new DrawBox(); // lower left
        DrawBox b = new DrawBox(); // lower right
        DrawBox c = new DrawBox(); // upper right
        DrawBox d = new DrawBox(); // upper left
    }
    private final BoundingBox bbox = new BoundingBox();

    /**
     * Constuctor:
     */
    public Delaunay() {

        bbox.minx = Integer.MAX_VALUE;
        bbox.maxx = Integer.MIN_VALUE;
        bbox.miny = Integer.MAX_VALUE;
        bbox.maxy = Integer.MIN_VALUE;

        // create the QuadEdge graph of the bounding box
        QuadEdge ab = QuadEdge.makeEdge(bbox.a, bbox.b);
        QuadEdge bc = QuadEdge.makeEdge(bbox.b, bbox.c);
        QuadEdge cd = QuadEdge.makeEdge(bbox.c, bbox.d);
        QuadEdge da = QuadEdge.makeEdge(bbox.d, bbox.a);
        QuadEdge.splice(ab.sym(), bc);
        QuadEdge.splice(bc.sym(), cd);
        QuadEdge.splice(cd.sym(), da);
        QuadEdge.splice(da.sym(), ab);

        this.startingEdge = ab;
    }

    public void setBoundingBox(int minx, int miny, int maxx, int maxy) {
        // update saved values
        bbox.minx = minx;
        bbox.maxx = maxx;
        bbox.miny = miny;
        bbox.maxy = maxy;

        // extend the bounding-box to surround min/max
        int centerx = (minx + maxx) / 2;
        int centery = (miny + maxy) / 2;
        int x_min = (int) ((minx - centerx - 1) * 10 + centerx);
        int x_max = (int) ((maxx - centerx + 1) * 10 + centerx);
        int y_min = (int) ((miny - centery - 1) * 10 + centery);
        int y_max = (int) ((maxy - centery + 1) * 10 + centery);

        // set new positions
        bbox.a.rect.x = x_min;
        bbox.a.rect.y = y_min;
        bbox.b.rect.x = x_max;
        bbox.b.rect.y = y_min;
        bbox.c.rect.x = x_max;
        bbox.c.rect.y = y_max;
        bbox.d.rect.x = x_min;
        bbox.d.rect.y = y_max;
    }

    // update the size of the bounding box (cf locate() method)
    private void updateBoundingBox(DrawBox p) {
        int minx = Math.min(bbox.minx, p.rect.x);
        int maxx = Math.max(bbox.maxx, p.rect.x);
        int miny = Math.min(bbox.miny, p.rect.y);
        int maxy = Math.max(bbox.maxy, p.rect.y);
        setBoundingBox(minx, miny, maxx, maxy);
        System.out.println("resizing bounding-box: "+minx+" "+miny+" "+maxx+" "+maxy);
    }

    private QuadEdge locate(DrawBox p) {

        /* outside the bounding box ? */
        if (p.rect.x < bbox.minx || p.rect.x > bbox.maxx || p.rect.y < bbox.miny || p.rect.y > bbox.maxy) {
            updateBoundingBox(p);
        }

        QuadEdge e = startingEdge;
        while (true) {
            /* duplicate point ? */
            if (p.rect.x == e.orig().rect.x && p.rect.y == e.orig().rect.y) {
                return e;
            }
            if (p.rect.x == e.dest().rect.x && p.rect.y == e.dest().rect.y) {
                return e;
            }

            /* walk */
            if (QuadEdge.isAtRightOf(e, p)) {
                e = e.sym();
            } else if (!QuadEdge.isAtRightOf(e.onext(), p)) {
                e = e.onext();
            } else if (!QuadEdge.isAtRightOf(e.dprev(), p)) {
                e = e.dprev();
            } else {
                return e;
            }
        }
    }

    public void insertDrawBox(DrawBox p) {
        QuadEdge e = locate(p);

        // point is a duplicate -> nothing to do
        if (p.rect.x == e.orig().rect.x && p.rect.y == e.orig().rect.y) {
            return;
        }
        if (p.rect.x == e.dest().rect.x && p.rect.y == e.dest().rect.y) {
            return;
        }

        // point is on an existing edge -> remove the edge
        if (QuadEdge.isOnLine(e, p)) {
            e = e.oprev();
            this.quadEdge.remove(e.onext().sym());
            this.quadEdge.remove(e.onext());
            QuadEdge.deleteEdge(e.onext());
        }

		// Connect the new point to the vertices of the containing triangle
        // (or quadrilateral in case of the point is on an existing edge)
        QuadEdge base = QuadEdge.makeEdge(e.orig(), p);
        this.quadEdge.add(base);

        QuadEdge.splice(base, e);
        this.startingEdge = base;
        do {
            base = QuadEdge.connect(e, base.sym());
            this.quadEdge.add(base);
            e = base.oprev();
        } while (e.lnext() != startingEdge);

        // Examine suspect edges to ensure that the Delaunay condition is satisfied.
        do {
            QuadEdge t = e.oprev();

            if (QuadEdge.isAtRightOf(e, t.dest())
                    && QuadEdge.inCircle(e.orig(), t.dest(), e.dest(), p)) {
                // flip triangles
                QuadEdge.swapEdge(e);
                e = e.oprev();
            } else if (e.onext() == startingEdge) {
                return; // no more suspect edges
            } else {
                e = e.onext().lprev();  // next suspect edge
            }
        } while (true);
    }

    public List<DrawBox[]> computeEdges() {
        List<DrawBox[]> edges = new ArrayList<>();
        // do not return edges pointing to/from surrouding triangle
        for (QuadEdge q : this.quadEdge) {
            if (q.orig() == bbox.a || q.orig() == bbox.b || q.orig() == bbox.c || q.orig() == bbox.d) {
                continue;
            }
            if (q.dest() == bbox.a || q.dest() == bbox.b || q.dest() == bbox.c || q.dest() == bbox.d) {
                continue;
            }
            edges.add(new DrawBox[]{q.orig(), q.dest()});
        }
        return edges;
    }

//    public List<DrawBox[]> computeTriangles() {
//        List<DrawBox[]> triangles = new ArrayList<>();
//
//		// do not process edges pointing to/from surrouding triangle
//        // --> mark them as already computed
//        for (QuadEdge q : this.quadEdge) {
//            q.mark = false;
//            q.sym().mark = false;
//            if (q.orig() == bbox.a || q.orig() == bbox.b || q.orig() == bbox.c || q.orig() == bbox.d) {
//                q.mark = true;
//            }
//            if (q.dest() == bbox.a || q.dest() == bbox.b || q.dest() == bbox.c || q.dest() == bbox.d) {
//                q.sym().mark = true;
//            }
//        }
//
//        // compute the 2 triangles associated to each quadEdge
//        for (QuadEdge qe : quadEdge) {
//            // first triangle
//            QuadEdge q1 = qe;
//            QuadEdge q2 = q1.lnext();
//            QuadEdge q3 = q2.lnext();
//            if (!q1.mark && !q2.mark && !q3.mark) {
//                triangles.add(new DrawBox[]{q1.orig(), q2.orig(), q3.orig()});
//            }
//
//            // second triangle
//            QuadEdge qsym1 = qe.sym();
//            QuadEdge qsym2 = qsym1.lnext();
//            QuadEdge qsym3 = qsym2.lnext();
//            if (!qsym1.mark && !qsym2.mark && !qsym3.mark) {
//                triangles.add(new DrawBox[]{qsym1.orig(), qsym2.orig(), qsym3.orig()});
//            }
//
//            // mark as used
//            qe.mark = true;
//            qe.sym().mark = true;
//        }
//
//        return triangles;
//    }

//    public List<DrawBox[]> computeVoronoi() {
//        List<DrawBox[]> voronoi = new ArrayList<>();
//
//		// do not process edges pointing to/from surrouding triangle
//        // --> mark them as already computed
//        for (QuadEdge q : this.quadEdge) {
//            q.mark = false;
//            q.sym().mark = false;
//            if (q.orig() == bbox.a || q.orig() == bbox.b || q.orig() == bbox.c || q.orig() == bbox.d) {
//                q.mark = true;
//            }
//            if (q.dest() == bbox.a || q.dest() == bbox.b || q.dest() == bbox.c || q.dest() == bbox.d) {
//                q.sym().mark = true;
//            }
//        }
//
//        for (QuadEdge qe : quadEdge) {
//
//            // walk throught left and right region
//            for (int b = 0; b <= 1; b++) {
//                QuadEdge qstart = (b == 0) ? qe : qe.sym();
//                if (qstart.mark) {
//                    continue;
//                }
//
//                // new region start
//                List<DrawBox> poly = new ArrayList<>();
//
//                // walk around region
//                QuadEdge qregion = qstart;
//                while (true) {
//                    qregion.mark = true;
//
//                    // compute CircumCenter if needed
//                    if (qregion.rot().orig() == null) {
//                        QuadEdge q1 = qregion;
//                        DrawBox p0 = q1.orig();
//                        QuadEdge q2 = q1.lnext();
//                        DrawBox p1 = q2.orig();
//                        QuadEdge q3 = q2.lnext();
//                        DrawBox p2 = q3.orig();
//
//                        double ex = p1.x - p0.x, ey = p1.y - p0.y;
//                        double nx = p2.y - p1.y, ny = p1.x - p2.x;
//                        double dx = (p0.x - p2.x) * 0.5, dy = (p0.y - p2.y) * 0.5;
//                        double s = (ex * dx + ey * dy) / (ex * nx + ey * ny);
//                        double cx = (p1.x + p2.x) * 0.5 + s * nx;
//                        double cy = (p1.y + p2.y) * 0.5 + s * ny;
//
//                        DrawBox p = new DrawBox((int) cx, (int) cy);
//                        qregion.rot().setOrig(p);
//                    }
//
//                    poly.add(qregion.rot().orig());
//
//                    qregion = qregion.onext();
//                    if (qregion == qstart) {
//                        break;
//                    }
//                }
//
//                // add region to output list
//                voronoi.add(poly.toArray(new DrawBox[0]));
//            }
//        }
//        return voronoi;
//    }
}
